package com.lwl.Algorithmic_data_structure.class17经典递归;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lwl
 * @Description 获取字符串的全排列, 去重版
 * @date 2023/6/2 20:12
 */
public class Code04getAllPermutations2 {

    public static void main(String[] args) {
        for (String a : getAllPermutations("abbc")) {
            System.out.println(a);
        }
    }

    static public List<String> getAllPermutations(String str) {
        char[] chars = str.toCharArray();
        ArrayList<String> ans = new ArrayList<>();
        process(chars, 0, ans);
        return ans;
    }

    static private void process(char[] chars, int curIdx, ArrayList<String> ans) {
        if (curIdx == chars.length) {
            ans.add(String.valueOf(chars));
            return;
        }
        // 换过就不要换了
        boolean[] visited = new boolean[256];
        for (int i = curIdx; i < chars.length; i++) {
            if (!visited[chars[i]]) {
                visited[chars[i]] = true;
                swap(curIdx, i, chars);
                process(chars, curIdx + 1, ans);
                swap(i, curIdx, chars);
            }
        }

    }

    static private void swap(int i, int j, char[] chars) {
        char t = chars[i];
        chars[i] = chars[j];
        chars[j] = t;
    }


}
